//
// Description: 295. 数据流的中位数
// Created by Loading on 2021/8/27.
//

#include <bits/stdc++.h>

using namespace std;

class MedianFinder {
    // 小于等于中位数的 优先级队列，降序
    priority_queue<int> qMin;
    // 大于中位数的 优先级队列，升序
    priority_queue<int, vector<int>, greater<>> qMax;
public:
    /** initialize your data structure here. */
    MedianFinder() = default;

    void addNum(int num) {
        if (qMin.empty() || num <= qMin.top()) {
            qMin.emplace(num);
            // 两个队列最多相差一个元素
            if (qMin.size() - qMax.size() > 1) {
                qMax.emplace(qMin.top());
                qMin.pop();
            }
        } else {
            qMax.emplace(num);
            // qMax 队列长度只能小于等于 qMin 队列长度
            if (qMax.size() > qMin.size()) {
                qMin.emplace(qMax.top());
                qMax.pop();
            }
        }
    }

    double findMedian() {
        // 数据流中 数据个数为偶数，取两个队头均值
        if (qMax.size() == qMin.size()) {
            return (qMin.top() + qMax.top()) / 2.0;
        }
        // 数据流中 数据个数为奇数，qMin 队头为中位数
        return qMin.top();
    }
};

int main() {
    MedianFinder obj;
    obj.addNum(1);
    double median = obj.findMedian();
    cout << median << endl;
    obj.addNum(2);
    median = obj.findMedian();
    cout << median << endl;
    obj.addNum(3);
    median = obj.findMedian();
    cout << median << endl;

    return 0;
}